# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrderBottom(self, root: TreeNode):
        queue, cur = [], [root]
        while cur:
            cur_layer_value = []
            next_layer_nodes = []
            for node in cur:
                if node:
                    cur_layer_value.append(node.val)
                    next_layer_nodes.extend([node.left, node.right])
            cur = next_layer_nodes
            if cur_layer_value:
                queue.insert(0, cur_layer_value)

        return queue


if __name__ == '__main__':
    root = TreeNode(3)
    left1, right1 = TreeNode(9), TreeNode(20)
    left2, right2 = TreeNode(15), TreeNode(7)
    root.left, root.right = left1, right1
    right1.left, right1.right = left2, right2
    s = Solution()
    result = s.levelOrderBottom(root)
    print(result)